<?php
/**
 *  User：LRZ
 *  Date：2020/1/29
 *  Time：17:18
 */

/**
 *  1170.比较字符串最小字母出现频次
 *
 *  标签：数组
 *
 *  我们来定义一个函数 f(s)，其中传入参数 s 是一个非空字符串；该函数的功能是统计 s  中（按字典序比较）最小字母的出现频次。
 *  例如，若 s = "dcce"，那么 f(s) = 2，因为最小的字母是 "c"，它出现了 2 次。
 *  现在，给你两个字符串数组待查表 queries 和词汇表 words，请你返回一个整数数组 answer 作为答案，其中每个 answer[i] 是满足 f(queries[i]) < f(W) 的词的数目，W 是词汇表 words 中的词。
 *
 *  示例 1：
 *      输入：queries = ["cbd"], words = ["zaaaz"]
 *      输出：[1]
 *      解释：查询 f("cbd") = 1，而 f("zaaaz") = 3 所以 f("cbd") < f("zaaaz")。
 *
 *  示例 2：
 *      输入：queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
 *      输出：[1,2]
 *      解释：第一个查询 f("bbb") < f("aaaa")，第二个查询 f("aaa") 和 f("aaaa") 都 > f("cc")。
 *   
 *  提示：
 *      1 <= queries.length <= 2000
 *      1 <= words.length <= 2000
 *      1 <= queries[i].length, words[i].length <= 10
 *      queries[i][j], words[i][j] 都是小写英文字母
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/compare-strings-by-frequency-of-the-smallest-character
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$queries = ['bbb', 'cc'];
$words   = ['a', 'aa', 'aaa', 'aaaa'];
$res     = numSmallerByFrequency($queries, $words);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function numSmallerByFrequency($queries, $words)
{
    $res        = [];
    $queries = frequency($queries);
    $words   = frequency($words);

    foreach ($queries as $v) {
        $temp = 0;
        foreach ($words as $v2) {
            if ($v < $v2) {
                $temp++;
            }
        }
        $res[] = $temp;
    }
    return $res;
}

function frequency($param)
{
    $res = [];
    foreach ($param as $v) {
        $size  = strlen($v);
        $min   = $v[0];
        $count = 0;
        for ($i = 0; $i < $size; $i++) {
            if ($min > $v[$i]) {
                $min   = $v[$i];
                $count = 0;
            }
            if ($min === $v[$i]) {
                $count++;
            }
        }
        $res[] = $count;
    }
    return $res;
}